package com.wfm.leetcode.editor.cn;
public class P剑指Offer13机器人的运动范围{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    // 这个是一股脑先递归，然后再判断是否符合条件
//    int res=0;
//    public int movingCount(int m, int n, int k) {
//        boolean[][] visit = new boolean[m][n];
//        dfs(m,n,k,0,0,visit);
//        return res;
//
//    }
//    void dfs(int m, int n, int k,int i,int j,boolean[][] visit){
//        if(i<0||i>=m||j<0||j>=n|| visit[i][j]){
//            return;
//        }
//
//        if((i/10+i%10+j/10+j%10)>k){
//            return;
//        }
//        visit[i][j]=true;
//        res++;
//        dfs(m,n,k,i-1,j,visit);
//        dfs(m,n,k,i+1,j,visit);
//        dfs(m,n,k,i,j-1,visit);
//        dfs(m,n,k,i,j+1,visit);
//    }

    // 这个是递归前就判断各种条件，判断是否能进入
    int res=0;
    public int movingCount(int m, int n, int k) {
        boolean[][] visit = new boolean[m][n];
        dfs(m,n,k,0,0,visit);
        return res;

    }
    void dfs(int m, int n, int k,int i,int j,boolean[][] visit){
//        if(i<0||i>=m||j<0||j>=n|| visit[i][j]){
//            return;
//        }
//
//        if((i/10+i%10+j/10+j%10)>k){
//            return;
//        }
        visit[i][j]=true;
        res++;
        int[][] dir = new int[][]{{-1,0},{1,0},{0,1},{0,-1}};
        for (int d = 0; d < dir.length; d++) {
            int ni=i+dir[d][0],nj = j +dir[d][1];
            if(ni>=0&&ni<m&&nj>=0&&nj<n){
                if(!visit[ni][nj]&&(ni/10+ni%10+nj/10+nj%10)<=k){
                    dfs(m,n,k,ni,nj,visit);
                }
            }
        }
//        dfs(m,n,k,i-1,j,visit);
//        dfs(m,n,k,i+1,j,visit);
//        dfs(m,n,k,i,j-1,visit);
//        dfs(m,n,k,i,j+1,visit);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new P剑指Offer13机器人的运动范围().new Solution();
        System.out.println(solution.movingCount(2, 3, 1));
    }
}